require(GGally, quietly = TRUE)
require(reshape2, quietly = TRUE)
require(tidyverse, quietly = TRUE, warn.conflicts = FALSE)
package ‘tidyverse’ was built under R version 3.3.2package ‘tibble’ was built under R version 3.3.2package ‘tidyr’ was built under R version 3.3.2
library(ggfortify)
library(cluster)
library(ggdendro)
library(broom)
theme_set(theme_bw())
source("github-lib.R")
dw <- load_github_wide()
summary(dw)
   repository_language   ForkEvent       IssuesEvent       PushEvent      
 ActionScript:  1      Min.   : 1.000   Min.   : 1.000   Min.   :  1.000  
 Ada         :  1      1st Qu.: 1.509   1st Qu.: 3.437   1st Qu.:  7.052  
 Agda        :  1      Median : 2.083   Median : 4.750   Median :  9.314  
 ANTLR       :  1      Mean   : 2.454   Mean   : 7.311   Mean   : 10.921  
 Apex        :  1      3rd Qu.: 2.913   3rd Qu.: 7.269   3rd Qu.: 10.602  
 AppleScript :  1      Max.   :18.000   Max.   :63.000   Max.   :154.250  
 (Other)     :121                                                         
   WatchEvent    
 Min.   : 1.000  
 1st Qu.: 2.000  
 Median : 3.007  
 Mean   : 3.725  
 3rd Qu.: 4.636  
 Max.   :13.471  
                 
dw %>% 
    select(-repository_language) %>% 
    ggpairs()

 plot: [1,1] [====---------------------------------------------------------]  6% est: 0s 
 plot: [1,2] [========-----------------------------------------------------] 12% est: 1s 
 plot: [1,3] [===========--------------------------------------------------] 19% est: 2s 
 plot: [1,4] [===============----------------------------------------------] 25% est: 1s 
 plot: [2,1] [===================------------------------------------------] 31% est: 1s 
 plot: [2,2] [=======================--------------------------------------] 38% est: 1s 
 plot: [2,3] [===========================----------------------------------] 44% est: 1s 
 plot: [2,4] [==============================-------------------------------] 50% est: 1s 
 plot: [3,1] [==================================---------------------------] 56% est: 1s 
 plot: [3,2] [======================================-----------------------] 62% est: 1s 
 plot: [3,3] [==========================================-------------------] 69% est: 1s 
 plot: [3,4] [==============================================---------------] 75% est: 0s 
 plot: [4,1] [==================================================-----------] 81% est: 0s 
 plot: [4,2] [=====================================================--------] 88% est: 0s 
 plot: [4,3] [=========================================================----] 94% est: 0s 
 plot: [4,4] [=============================================================]100% est: 0s 
                                                                                         

# XML e Bluespec têm mais de 50 pushes / repositório e 
# outras linguagens têm também números estranhos. Filtraremos.
dw <- dw %>% 
  filter(PushEvent < 50, IssuesEvent < 50, ForkEvent < 18)

As variáveis são bastante assimétricas e concentradas em pequenos valores. Transformá-las para log ajuda na visualização.

summary(dw2.scaled)
   repository_language   ForkEvent         IssuesEvent         PushEvent      
 ActionScript:  1      Min.   :-1.80630   Min.   :-2.22415   Min.   :-5.1947  
 Ada         :  1      1st Qu.:-0.81777   1st Qu.:-0.46527   1st Qu.:-0.4681  
 Agda        :  1      Median :-0.01687   Median :-0.02479   Median : 0.1830  
 ANTLR       :  1      Mean   : 0.00000   Mean   : 0.00000   Mean   : 0.0000  
 Apex        :  1      3rd Qu.: 0.75644   3rd Qu.: 0.55363   3rd Qu.: 0.4992  
 AppleScript :  1      Max.   : 2.56203   Max.   : 2.76710   Max.   : 2.7606  
 (Other)     :115                                                             
   WatchEvent         cluster         
 Min.   :-1.88615   Length:121        
 1st Qu.:-0.72590   Class :character  
 Median :-0.04339   Mode  :character  
 Mean   : 0.00000                     
 3rd Qu.: 0.68503                     
 Max.   : 2.35217                     
                                      
dists = dw2.scaled %>% 
    column_to_rownames("repository_language") %>% 
    dist(method = "euclidean")
hc = hclust(dists, method = "ward.D")
plot(hc, cex = .6)

plot(hc, hang = -1)
n_clusters = 4
rect.hclust(hc, k=n_clusters)

dw2 <- dw2 %>% 
    mutate(cluster = hc %>% 
               cutree(k = n_clusters) %>% 
               as.character())
dw2.scaled <- dw2.scaled %>% 
    mutate(cluster = hc %>% 
               cutree(k = n_clusters) %>% 
               as.character())
dw2.long = melt(dw2.scaled, id.vars = c("repository_language", "cluster"))
hc %>% 
    cutree(k = n_clusters) %>% 
    silhouette(dists) %>% 
    plot(col = RColorBrewer::brewer.pal(n_clusters, "Set2"))

dw2.long %>% 
    ggplot(aes(x = variable, y = value, group = repository_language, colour = cluster)) + 
    geom_line(alpha = 0.4) + 
    facet_wrap(~ cluster) 

library(plotly)
p <- dw2 %>%
    plot_ly(type = 'parcoords',
            line = list(color = ~cluster),
            dimensions = list(
                #list(range = c(1, 4), label = "cluster", values = ~cluster),
                list(range = c(0, 4),
                     label = 'Sepal Width', values = ~ForkEvent),
                list(range = c(0, 4),
                     constraintrange = c(5,6),
                     label = 'Sepal Length', values = ~IssuesEvent),
                list(range = c(0, 4),
                     label = 'Petal Width', values = ~PushEvent),
                list(range = c(0, 4),
                     label = 'Petal Length', values = ~WatchEvent)
            )
    )
p

k-means

table(km %>% pull(cluster))
Error in function_list[[k]](value) : 
  não foi possível encontrar a função "pull"

Qual seria um bom valor de k? Uma medida comumente usada no kmeans é comparar a distância (quadrática) entre o centro dos clusters e o centro dos dados com a distância (quadrática) entre os pontos todos nos dados e o centro dos dados. Aqui o centro dos dados é um ponto imaginário na média de todas as variáveis. Calculamos a distância do centro de cada cluster para o centro dos dados e multiplicamos pelo número de pontos nesse cluster. Somando esse valor para todos os clusters, temos betweenss abaixo. Se esse valor for próximo do somatório total das distâncias dos pontos para o centro dos dados (totss), os pontos estão próximos do centro de seu cluster. Essa proporção pode ser usada para definir um bom valor de k. Quando ela para de crescer, para de valer à pena aumentar k.

set.seed(123)
explorando_k = tibble(k = 1:15) %>% 
    group_by(k) %>% 
    do(
        kmeans(select(dw2.scaled, -repository_language), 
               centers = .$k, 
               nstart = 20) %>% glance()
    )
explorando_k %>% 
    ggplot(aes(x = k, y = betweenss / totss)) + 
    geom_line() + 
    geom_point()


K-means

filmes = readr::read_csv("dados/filmes-scarlett-johanssson.csv")
Parsed with column specification:
cols(
  RATING = col_double(),
  TITLE = col_character(),
  CREDIT = col_character(),
  `BOX OFFICE` = col_double(),
  YEAR = col_integer()
)

Mais um exemplo

O dataset ruspini é clássico para ilustrar agrupamento.

Hierárquico

dists = dist(rs, method = "euclidean")
hc = hclust(dists, method = "ward.D")

plot(hc, hang = -1, cex = 0.8)

rect.hclust(hc, k=4)

rs$cluster = factor(cutree(hc, k=4))

ggplot(rs, aes(x = x, y = y, colour = cluster)) + 
  geom_point(size = 3) 

rs$cluster = factor(cutree(hc, k=8))
ggplot(rs, aes(x = x, y = y, colour = cluster, label = cluster)) + 
  geom_point(size = 2) + 
  geom_text(hjust = -.1, vjust = 1) + 
  xlim(0, 150)

plot(silhouette(cutree(hc, k = 4), dists))
plot(silhouette(cutree(hc, k = 6), dists))

#heatmap(as.matrix(dw2[,1:4]), Colv=F, scale='none')
#hc.data <- dendro_data(hc)
#ggdendrogram(hc.data, rotate = TRUE) + 
  #labs(title = "Agrupamento de Rustini")
km <- kmeans(rs, centers=4, nstart=10)
km

autoplot(km, data = rs)

autoplot(km, data = rs, frame = TRUE)
LS0tCnRpdGxlOiAiS21lYW5zIGUgbWFpcyBleGVtcGxvcyIKYXV0aG9yOiAiTmF6YXJlbm8gQW5kcmFkZSIKZGF0ZTogIjMwIGRlIG1hcsOnbyBkZSAyMDE2IgpvdXRwdXQ6IAogICAgaHRtbF9ub3RlYm9vawplZGl0b3Jfb3B0aW9uczogCiAgY2h1bmtfb3V0cHV0X3R5cGU6IGlubGluZQotLS0KCmBgYHtyLCBtZXNzYWdlPUZBTFNFfQpyZXF1aXJlKEdHYWxseSwgcXVpZXRseSA9IFRSVUUpCnJlcXVpcmUocmVzaGFwZTIsIHF1aWV0bHkgPSBUUlVFKQpyZXF1aXJlKHRpZHl2ZXJzZSwgcXVpZXRseSA9IFRSVUUsIHdhcm4uY29uZmxpY3RzID0gRkFMU0UpCmxpYnJhcnkoZ2dmb3J0aWZ5KQpsaWJyYXJ5KGNsdXN0ZXIpCmxpYnJhcnkoZ2dkZW5kcm8pCmxpYnJhcnkoYnJvb20pCgp0aGVtZV9zZXQodGhlbWVfYncoKSkKc291cmNlKCJnaXRodWItbGliLlIiKQpgYGAKCmBgYHtyfQpkdyA8LSBsb2FkX2dpdGh1Yl93aWRlKCkKc3VtbWFyeShkdykKCmR3ICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgojIFhNTCBlIEJsdWVzcGVjIHTDqm0gbWFpcyBkZSA1MCBwdXNoZXMgLyByZXBvc2l0w7NyaW8gZSAKIyBvdXRyYXMgbGluZ3VhZ2VucyB0w6ptIHRhbWLDqW0gbsO6bWVyb3MgZXN0cmFuaG9zLiBGaWx0cmFyZW1vcy4KZHcgPC0gZHcgJT4lIAogIGZpbHRlcihQdXNoRXZlbnQgPCA1MCwgSXNzdWVzRXZlbnQgPCA1MCwgRm9ya0V2ZW50IDwgMTgpCmBgYAoKQXMgdmFyacOhdmVpcyBzw6NvIGJhc3RhbnRlIGFzc2ltw6l0cmljYXMgZSBjb25jZW50cmFkYXMgZW0gcGVxdWVub3MgdmFsb3Jlcy4gVHJhbnNmb3Jtw6EtbGFzIHBhcmEgbG9nIGFqdWRhIG5hIHZpc3VhbGl6YcOnw6NvLgoKYGBge3J9CiMgRXNjYWxhIGRlIGxvZyAKZHcyIDwtIGR3ICU+JSAKICAgIG11dGF0ZV9lYWNoKGZ1bnMobG9nKSwgMjo1KQoKZHcyICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgpzdW1tYXJ5KHNlbGVjdChkdzIsIC1yZXBvc2l0b3J5X2xhbmd1YWdlKSkKCmR3Mi5zY2FsZWQgPSBkdzIgJT4lIAogIG11dGF0ZV9lYWNoKGZ1bnMoYXMudmVjdG9yKHNjYWxlKC4pKSksIDI6NSkKc3VtbWFyeShkdzIuc2NhbGVkKQpgYGAKCgpgYGB7cn0KZGlzdHMgPSBkdzIuc2NhbGVkICU+JSAKICAgIGNvbHVtbl90b19yb3duYW1lcygicmVwb3NpdG9yeV9sYW5ndWFnZSIpICU+JSAKICAgIGRpc3QobWV0aG9kID0gImV1Y2xpZGVhbiIpCmhjID0gaGNsdXN0KGRpc3RzLCBtZXRob2QgPSAid2FyZC5EIikKCnBsb3QoaGMsIGNleCA9IC42KQpwbG90KGhjLCBoYW5nID0gLTEpCgpuX2NsdXN0ZXJzID0gNApyZWN0LmhjbHVzdChoYywgaz1uX2NsdXN0ZXJzKQoKZHcyIDwtIGR3MiAlPiUgCiAgICBtdXRhdGUoY2x1c3RlciA9IGhjICU+JSAKICAgICAgICAgICAgICAgY3V0cmVlKGsgPSBuX2NsdXN0ZXJzKSAlPiUgCiAgICAgICAgICAgICAgIGFzLmNoYXJhY3RlcigpKQoKZHcyLnNjYWxlZCA8LSBkdzIuc2NhbGVkICU+JSAKICAgIG11dGF0ZShjbHVzdGVyID0gaGMgJT4lIAogICAgICAgICAgICAgICBjdXRyZWUoayA9IG5fY2x1c3RlcnMpICU+JSAKICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKCkpCgpkdzIubG9uZyA9IG1lbHQoZHcyLnNjYWxlZCwgaWQudmFycyA9IGMoInJlcG9zaXRvcnlfbGFuZ3VhZ2UiLCAiY2x1c3RlciIpKQoKaGMgJT4lIAogICAgY3V0cmVlKGsgPSBuX2NsdXN0ZXJzKSAlPiUgCiAgICBzaWxob3VldHRlKGRpc3RzKSAlPiUgCiAgICBwbG90KGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbChuX2NsdXN0ZXJzLCAiU2V0MiIpKQoKZHcyLmxvbmcgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gdmFyaWFibGUsIHkgPSB2YWx1ZSwgZ3JvdXAgPSByZXBvc2l0b3J5X2xhbmd1YWdlLCBjb2xvdXIgPSBjbHVzdGVyKSkgKyAKICAgIGdlb21fbGluZShhbHBoYSA9IDAuNCkgKyAKICAgIGZhY2V0X3dyYXAofiBjbHVzdGVyKSAKCmBgYAoKYGBge3J9CmxpYnJhcnkocGxvdGx5KQpwIDwtIGR3MiAlPiUKICAgIHBsb3RfbHkodHlwZSA9ICdwYXJjb29yZHMnLAogICAgICAgICAgICBsaW5lID0gbGlzdChjb2xvciA9IH5jbHVzdGVyKSwKICAgICAgICAgICAgZGltZW5zaW9ucyA9IGxpc3QoCiAgICAgICAgICAgICAgICAjbGlzdChyYW5nZSA9IGMoMSwgNCksIGxhYmVsID0gImNsdXN0ZXIiLCB2YWx1ZXMgPSB+Y2x1c3RlciksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygwLCA0KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnRm9ya3MvcmVwbycsIHZhbHVlcyA9IH5Gb3JrRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGNvbnN0cmFpbnRyYW5nZSA9IGMoNSw2KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnSXNzdWVzL3JlcG8nLCB2YWx1ZXMgPSB+SXNzdWVzRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ1B1c2hlcy9yZXBvJywgdmFsdWVzID0gflB1c2hFdmVudCksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygwLCA0KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnV2F0Y2hlcy9yZXBvJywgdmFsdWVzID0gfldhdGNoRXZlbnQpCiAgICAgICAgICAgICkKICAgICkKcApgYGAKCgojIyBrLW1lYW5zCgpgYGB7cn0KZHcyLnNjYWxlZCA9IGR3Mi5zY2FsZWQgJT4lIAogICAgc2VsZWN0KC1jbHVzdGVyKSAjIFJlbW92ZSBvIGNsdXN0ZXIgYWRpY2lvbmFkbyBhbnRlcyBsw6EgZW0gY2ltYSB2aWEgaGNsdXN0CgojIE8gYWdydXBhbWVudG8gZGUgZmF0bzoKa20gPSBkdzIuc2NhbGVkICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAga21lYW5zKGNlbnRlcnMgPSBuX2NsdXN0ZXJzLCBuc3RhcnQgPSAyMCkKCiMgTyBkZiBlbSBmb3JtYXRvIGxvbmdvLCBwYXJhIHZpc3VhbGl6YcOnw6NvIApkdzIuc2NhbGVkLmttLmxvbmcgPSBrbSAlPiUgCiAgICBhdWdtZW50KGR3Mi5zY2FsZWQpICU+JSAjIEFkaWNpb25hIG8gcmVzdWx0YWRvIGRlIGttIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBhb3MgZGFkb3Mgb3JpZ2luYWlzIGR3Mi5zY2FsZWQgZW0gCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHVtYSB2YXJpw6F2ZWwgY2hhbWFkYSAuY2x1c3RlcgogICAgZ2F0aGVyKGtleSA9ICJ2YXJpw6F2ZWwiLCAKICAgICAgICAgICB2YWx1ZSA9ICJ2YWxvciIsIAogICAgICAgICAgIC1yZXBvc2l0b3J5X2xhbmd1YWdlLCAtLmNsdXN0ZXIpICMgPSBtb3ZlIHBhcmEgbG9uZyB0b2RhcyBhcyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHZhcmnDoXZpZXMgbWVub3MgcmVwb3NpdG9yeV9sYW5ndWFnZSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIGUgLmNsdXN0ZXIKCmR3Mi5zY2FsZWQua20ubG9uZyAlPiUgCiAgICBnZ3Bsb3QoYWVzKHggPSBgdmFyacOhdmVsYCwgeSA9IHZhbG9yLCBncm91cCA9IHJlcG9zaXRvcnlfbGFuZ3VhZ2UsIGNvbG91ciA9IC5jbHVzdGVyKSkgKyAKICAgIGdlb21fcG9pbnQoYWxwaGEgPSAwLjIpICsgCiAgICBnZW9tX2xpbmUoYWxwaGEgPSAuNSkgKyAKICAgIGZhY2V0X3dyYXAofiAuY2x1c3RlcikgCgphdXRvcGxvdChrbSwgZGF0YSA9IGR3Mi5zY2FsZWQsIGxhYmVsID0gVFJVRSkKCmRpc3RzID0gZHcyLnNjYWxlZCAlPiUgCiAgICBzZWxlY3QoLXJlcG9zaXRvcnlfbGFuZ3VhZ2UpICU+JSAKICAgIGRpc3QoKSAjIHPDsyBwYXJhIHBsb3RhciBzaWxob3VldGFzIGRlcG9pcwpwbG90KHNpbGhvdWV0dGUoa20kY2x1c3RlciwgZGlzdHMpLCBjb2wgPSBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwobl9jbHVzdGVycywgIlNldDIiKSkKCnRhYmxlKGttICU+JSBwdWxsKGNsdXN0ZXIpKQpgYGAKCmBgYHtyfQojc3VtbWFyeShkdzIuc2NhbGVkKQpwIDwtIGttICU+JSAKICAgIGF1Z21lbnQoZHcyLnNjYWxlZCkgJT4lCiAgICBwbG90X2x5KHR5cGUgPSAncGFyY29vcmRzJywKICAgICAgICAgICAgbGluZSA9IGxpc3QoY29sb3IgPSB+LmNsdXN0ZXIsIAogICAgICAgICAgICAgICAgICAgICAgICBzaG93U2NhbGUgPSBUUlVFKSwKICAgICAgICAgICAgZGltZW5zaW9ucyA9IGxpc3QoCiAgICAgICAgICAgICAgICAjbGlzdChyYW5nZSA9IGMoMSwgNCksIGxhYmVsID0gImNsdXN0ZXIiLCB2YWx1ZXMgPSB+Y2x1c3RlciksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygtMywgMyksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ0ZvcmtzL3JlcG8nLCB2YWx1ZXMgPSB+Rm9ya0V2ZW50KSwKICAgICAgICAgICAgICAgIGxpc3QocmFuZ2UgPSBjKC0zLCAzKSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnSXNzdWVzL3JlcG8nLCB2YWx1ZXMgPSB+SXNzdWVzRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoLTYsIDMpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdQdXNoZXMvcmVwbycsIHZhbHVlcyA9IH5QdXNoRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoLTIsIDMpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdXYXRjaGVzL3JlcG8nLCB2YWx1ZXMgPSB+V2F0Y2hFdmVudCkKICAgICAgICAgICAgKQogICAgKQpwCgpgYGAKClF1YWwgc2VyaWEgdW0gYm9tIHZhbG9yIGRlIGs/IFVtYSBtZWRpZGEgY29tdW1lbnRlIHVzYWRhIG5vIGttZWFucyDDqSBjb21wYXJhciBhIGRpc3TDom5jaWEgKHF1YWRyw6F0aWNhKSBlbnRyZSBvIGNlbnRybyBkb3MgY2x1c3RlcnMgZSBvIGNlbnRybyBkb3MgZGFkb3MgY29tIGEgZGlzdMOibmNpYSAocXVhZHLDoXRpY2EpIGVudHJlIG9zIHBvbnRvcyB0b2RvcyBub3MgZGFkb3MgZSBvIGNlbnRybyBkb3MgZGFkb3MuIEFxdWkgbyBjZW50cm8gZG9zIGRhZG9zIMOpIHVtIHBvbnRvIGltYWdpbsOhcmlvIG5hIG3DqWRpYSBkZSB0b2RhcyBhcyB2YXJpw6F2ZWlzLiBDYWxjdWxhbW9zIGEgZGlzdMOibmNpYSBkbyBjZW50cm8gZGUgY2FkYSBjbHVzdGVyIHBhcmEgbyBjZW50cm8gZG9zIGRhZG9zIGUgbXVsdGlwbGljYW1vcyBwZWxvIG7Dum1lcm8gZGUgcG9udG9zIG5lc3NlIGNsdXN0ZXIuIFNvbWFuZG8gZXNzZSB2YWxvciBwYXJhIHRvZG9zIG9zIGNsdXN0ZXJzLCB0ZW1vcyBgYmV0d2VlbnNzYCBhYmFpeG8uIFNlIGVzc2UgdmFsb3IgZm9yIHByw7N4aW1vIGRvIHNvbWF0w7NyaW8gdG90YWwgZGFzIGRpc3TDom5jaWFzIGRvcyBwb250b3MgcGFyYSBvIGNlbnRybyBkb3MgZGFkb3MgKGB0b3Rzc2ApLCBvcyBwb250b3MgZXN0w6NvIHByw7N4aW1vcyBkbyBjZW50cm8gZGUgc2V1IGNsdXN0ZXIuIApFc3NhIHByb3BvcsOnw6NvIHBvZGUgc2VyIHVzYWRhIHBhcmEgZGVmaW5pciB1bSBib20gdmFsb3IgZGUgYGtgLiBRdWFuZG8gZWxhIHBhcmEgZGUgY3Jlc2NlciwgcGFyYSBkZSB2YWxlciDDoCBwZW5hIGF1bWVudGFyIGBrYC4KCmBgYHtyfQpzZXQuc2VlZCgxMjMpCmV4cGxvcmFuZG9fayA9IHRpYmJsZShrID0gMToxNSkgJT4lIAogICAgZ3JvdXBfYnkoaykgJT4lIAogICAgZG8oCiAgICAgICAga21lYW5zKHNlbGVjdChkdzIuc2NhbGVkLCAtcmVwb3NpdG9yeV9sYW5ndWFnZSksIAogICAgICAgICAgICAgICBjZW50ZXJzID0gLiRrLCAKICAgICAgICAgICAgICAgbnN0YXJ0ID0gMjApICU+JSBnbGFuY2UoKQogICAgKQoKZXhwbG9yYW5kb19rICU+JSAKICAgIGdncGxvdChhZXMoeCA9IGssIHkgPSBiZXR3ZWVuc3MgLyB0b3RzcykpICsgCiAgICBnZW9tX2xpbmUoKSArIAogICAgZ2VvbV9wb2ludCgpCmBgYAoKCi0tLS0tLS0tLS0tLS0tLS0tLS0tCgoKIyMgSy1tZWFucwoKYGBge3J9CmZpbG1lcyA9IHJlYWRyOjpyZWFkX2NzdigiZGFkb3MvZmlsbWVzLXNjYXJsZXR0LWpvaGFuc3Nzb24uY3N2IikKCmZpbG1lc190ID0gZmlsbWVzICU+JSAKICAgIHNlbGVjdCgtQ1JFRElUKSAlPiUgCiAgICBtdXRhdGUoYEJPWCBPRkZJQ0VgID0gbG9nMTAoYEJPWCBPRkZJQ0VgKSkgJT4lIAogICAgbXV0YXRlX2VhY2goZnVucyhhcy52ZWN0b3Ioc2NhbGUoLikpKSwgYEJPWCBPRkZJQ0VgLCBSQVRJTkcpCgphdHJpYnVpY29lcyA9IHRpYmJsZShrID0gMTo2KSAlPiUgCiAgICBncm91cF9ieShrKSAlPiUgCiAgICBkbyhrbWVhbnMoc2VsZWN0KGZpbG1lc190LCBSQVRJTkcsIGBCT1ggT0ZGSUNFYCksIAogICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgIG5zdGFydCA9IDEwKSAlPiUgYXVnbWVudChmaWxtZXMpKSAjIGFsdGVybmUgZW50cmUgZmlsbWVzIGUgZmlsbWVzX3Qgbm8gYXVnbWVudCAgCgphdHJpYnVpY29lc19sb25nID0gYXRyaWJ1aWNvZXMgJT4lIAogICAgZ2F0aGVyKGtleSA9ICJ2YXJpYXZlbCIsIHZhbHVlID0gInZhbG9yIiwgLVRJVExFLCAtaywgLS5jbHVzdGVyLCAtQ1JFRElUKSAKCmF0cmlidWljb2VzICU+JQogICAgZ2dwbG90KGFlcyh4ID0gUkFUSU5HLCB5ID0gYEJPWC5PRkZJQ0VgLCBsYWJlbCA9IFRJVExFLCBjb2xvdXIgPSAuY2x1c3RlcikpICsgCiAgICBnZW9tX3BvaW50KCkgKyAKICAgICNnZW9tX3RleHQoKSArIAogICAgZmFjZXRfd3JhcCh+IGspCiAgICAjKyBzY2FsZV95X2xvZzEwKCkKCiMgQSBzaWxob3VldGEKZGlzdHMgPSBzZWxlY3QoZmlsbWVzX3QsIFJBVElORywgYEJPWCBPRkZJQ0VgKSAlPiUgZGlzdCgpCmttID0ga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgUkFUSU5HLCBgQk9YIE9GRklDRWApLCAKICAgICAgICAgICAgY2VudGVycyA9IDQsIAogICAgICAgICAgICBuc3RhcnQgPSAxMCkgCgpzaWxob3VldHRlKGttJGNsdXN0ZXIsIGRpc3RzKSAlPiUgCiAgICBwbG90KGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg0LCAiU2V0MiIpKQpgYGAKCmBgYHtyfQpzZXQuc2VlZCgxMjMpCmV4cGxvcmFuZG9fayA9IHRpYmJsZShrID0gMToxNSkgJT4lIAogICAgZ3JvdXBfYnkoaykgJT4lIAogICAgZG8oCiAgICAgICAga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgLVRJVExFKSwgCiAgICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgICBuc3RhcnQgPSAyMCkgJT4lIGdsYW5jZSgpCiAgICApCgpleHBsb3JhbmRvX2sgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IGJldHdlZW5zcyAvIHRvdHNzKSkgKyAKICAgIGdlb21fbGluZSgpICsgCiAgICBnZW9tX3BvaW50KCkKCmBgYAoKCiMgTWFpcyB1bSBleGVtcGxvCgpPIGRhdGFzZXQgcnVzcGluaSDDqSBjbMOhc3NpY28gcGFyYSBpbHVzdHJhciBhZ3J1cGFtZW50by4KCmBgYHtyfQpzdHIocnVzcGluaSkKCmdncGxvdChydXNwaW5pLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKc3VtbWFyeShydXNwaW5pKQoKcnMgPC0gZGF0YS5mcmFtZSgocnVzcGluaSkpCnJzIDwtIGRhdGEuZnJhbWUoc2NhbGUocnVzcGluaSkpCmNvbE1lYW5zKHJzKQoKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKYGBgCgojIyBIaWVyw6FycXVpY28KCmBgYHtyfQpkaXN0cyA9IGRpc3QocnMsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQpoYyA9IGhjbHVzdChkaXN0cywgbWV0aG9kID0gIndhcmQuRCIpCgpwbG90KGhjLCBoYW5nID0gLTEsIGNleCA9IDAuOCkKCnJlY3QuaGNsdXN0KGhjLCBrPTQpCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz00KSkKCmdncGxvdChycywgYWVzKHggPSB4LCB5ID0geSwgY29sb3VyID0gY2x1c3RlcikpICsgCiAgZ2VvbV9wb2ludChzaXplID0gMykgCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz04KSkKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvdXIgPSBjbHVzdGVyLCBsYWJlbCA9IGNsdXN0ZXIpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIpICsgCiAgZ2VvbV90ZXh0KGhqdXN0ID0gLS4xLCB2anVzdCA9IDEpICsgCiAgeGxpbSgwLCAxNTApCgpwbG90KHNpbGhvdWV0dGUoY3V0cmVlKGhjLCBrID0gNCksIGRpc3RzKSkKcGxvdChzaWxob3VldHRlKGN1dHJlZShoYywgayA9IDYpLCBkaXN0cykpCgojaGVhdG1hcChhcy5tYXRyaXgoZHcyWywxOjRdKSwgQ29sdj1GLCBzY2FsZT0nbm9uZScpCiNoYy5kYXRhIDwtIGRlbmRyb19kYXRhKGhjKQojZ2dkZW5kcm9ncmFtKGhjLmRhdGEsIHJvdGF0ZSA9IFRSVUUpICsgCiAgI2xhYnModGl0bGUgPSAiQWdydXBhbWVudG8gZGUgUnVzdGluaSIpCmBgYAoKYGBge3J9CmttIDwtIGttZWFucyhycywgY2VudGVycz00LCBuc3RhcnQ9MTApCmttCgphdXRvcGxvdChrbSwgZGF0YSA9IHJzKQoKYXV0b3Bsb3Qoa20sIGRhdGEgPSBycywgZnJhbWUgPSBUUlVFKQoKYGBgCgo=